package com.hyper_yang.algorithmRecord;

import java.util.HashMap;

public class LeetCode_76 {
    /*   最小覆盖字串
    给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
      注意：对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。      如果 s 中存在这样的子串，我们保证它是唯一的答案。
     */
    public static void main(String[] args) {
        System.out.println(temp("ADOBECODEBANC", "ABC"));
//        System.out.println(minWindow("ADOBECODEBANC", "ABC"));
    }
    // 方法一: 枚举 s中所有字串   O(n^3)
    public static String minWindow1(String s, String t) {
        // 定义最小字串，保存结果，初始为空字符串
        String minSubString = "";
        // 保存 t中字符出现的频次
        HashMap<Character, Integer> tCharFrequency = new HashMap<>();
        // 统计 t中字符频次
        for (char c : t.toCharArray()) {
            tCharFrequency.put(c, tCharFrequency.getOrDefault(c,0) + 1);
        }
        // 在 s中搜索所有覆盖子串
        // 遍历所有字符，作为当前字串的起始位置
        for (int i = 0; i < s.length(); i++) {
            // 遍历 i之后不小于 t长度的位置，作为字串结束位置（因为找的到满足要求的字串，target.length()一定是 >= t.length()的）
            for (int j = i + t.length(); j <= s.length(); j++) { // j - i 为截取的 subStr大小
                // 统计 s子串中每个字符出现的频次
                HashMap<Character, Integer> subCharFrequency = new HashMap<>();
                for (int k = i; k < j; k++) {
                    char c = s.charAt(k);
                    subCharFrequency.put(c, subCharFrequency.getOrDefault(c,0) + 1);
                }
                // 如果当前子串符合覆盖字串的要求，并且比之前的最小字串小就替换
                if (check(tCharFrequency,subCharFrequency) && (minSubString.equals("") || j - i < minSubString.length())) {
                    minSubString = s.substring(i, j);
                }
            }
        }
        return minSubString;
    }
    // 方法二: 滑动窗口   O(n^2)
    public static String minWindow2(String s, String t) {
        // 定义最小字串，保存结果，初始为空字符串
        String minSubString = "";
        // 统计 t中字符频次
        HashMap<Character, Integer> tCharFrequency = new HashMap<>();
        for (char c : t.toCharArray()) {
            tCharFrequency.put(c, tCharFrequency.getOrDefault(c,0) + 1);
        }
        // 定义左右指针，指向滑动窗口的起始和结束位置
        int start = 0, end = t.length();
        while (end <= s.length()) {
            // 统计 s子串中字符频次
            HashMap<Character, Integer> subCharFrequency = new HashMap<>();
            for (int k = start; k < end; k++) {
                char c = s.charAt(k);
                subCharFrequency.put(c, subCharFrequency.getOrDefault(c,0) + 1);
            }
            // 如果当前子串符合覆盖子串的要求，并且比之前的最小字串小就替换
            if (check(tCharFrequency,subCharFrequency)) { // 找到可行解
                if (minSubString.equals("") || end - start < minSubString.length()) {
                    minSubString = s.substring(start, end);
                }
                // 只要是覆盖子串，就移动初始位置，缩小窗口，寻找当前局部最优解
                start++; // 寻找局部最优解
            } else {
                // 不是覆盖子串，扩大窗口
                end++; // 没找到局部最优解，扩大寻找范围
            }
        }
        return minSubString;
    }
    // 方法三: 滑动窗口优化
    public static String minWindow3(String s, String t) {
        String minSubString="";
        HashMap<Character,Integer> tMap = new HashMap<>();
        for (char c : t.toCharArray()){
            tMap.put(c,tMap.getOrDefault(c,0) +1);
        }
        int start = 0, end = 1;
        // 在原先 s字串集合上进行更改即可
        HashMap<Character,Integer> subStrMap = new HashMap<>();
        while (end <= s.length()) {
            // end增加之后，新增的字符
            char newChar = s.charAt(end - 1);
            // 新增因素字符频次 +1  (小优化: 只考虑 t中存在的 or 会有影响的字符)
            if (tMap.containsKey(newChar)) subStrMap.put(newChar,subStrMap.getOrDefault(newChar,0) + 1);
            // 判断是否满足要求,符合要求一直删都可以,这时要考虑到start、end重合的情况。
            while (check(tMap, subStrMap) && start < end){ // O(C)
                if (minSubString.equals("") || end - start < minSubString.length()) {
                    minSubString = s.substring(start, end);
                }
                // 对要删除的字符，频次 -1
                char removedChar = s.charAt(start);
                // 同样的，没影响的字符无所谓   ps: 这里的字串一定有，可以不需要 default
                if (tMap.containsKey(removedChar)) subStrMap.put(removedChar,subStrMap.get(removedChar) - 1);
                start++;
            }
            end++;
        }
        return minSubString;
    }
    // 优化:
    public static String minWindow(String s, String t) {
        String minSubString="";
        HashMap<Character,Integer> tMap = new HashMap<>();
        for (char c : t.toCharArray()){
            tMap.put(c,tMap.getOrDefault(c,0) +1);
        }
        int start = 0, end = 1;
        // 在原先 s字串集合上进行更改即可
        HashMap<Character,Integer> subStrMap = new HashMap<>();
        // 定义 "字串贡献值"，统计 t中的字符在子串中出现了多少
        int charCount = 0;
        while (end <= s.length()) {
            // end增加之后，新增的字符
            char newChar = s.charAt(end - 1);
            // 新增因素字符频次 +1  (小优化: 只考虑 t中存在的 or 会有影响的字符)
            if (tMap.containsKey(newChar)) {
                subStrMap.put(newChar,subStrMap.getOrDefault(newChar,0) + 1);
                if (subStrMap.get(newChar) <= tMap.get(newChar)) charCount++;
            }
            // 判断是否满足要求,符合要求一直删都可以,这时要考虑到start、end重合的情况。
            while (charCount == t.length() && start < end){ // O(C)
                if (minSubString.equals("") || end - start < minSubString.length()) {
                    minSubString = s.substring(start, end);
                }
                // 对要删除的字符，频次 -1
                char removedChar = s.charAt(start);
                // 同样的，没影响的字符无所谓   ps: 这里的字串一定有，可以不需要 default
                if (tMap.containsKey(removedChar)) {
                    subStrMap.put(removedChar,subStrMap.get(removedChar) - 1);
                    // 如果字串中的频次，已经达到了 t中的频次，贡献值就不变，如果不满足 t中的频次，说明减少了真正有贡献的值
                    if (subStrMap.get(removedChar) < tMap.get(removedChar)) charCount--;
                }
                start++;
            }
            end++;
        }
        return minSubString;
    }
    public static String temp(String s, String t) {
        String minSubString = "";
        HashMap<Character,Integer> tMap = new HashMap<>();
        for (char c : t.toCharArray()){
            tMap.put(c,tMap.getOrDefault(c,0)+1);
        }
        int start = 0, end = 0;
        HashMap<Character,Integer> subStrMap = new HashMap<>();
        while (end <= s.length()) {
            if(check(tMap,subStrMap)) {
                if (end-start < minSubString.length() || minSubString.isEmpty()) {
                    minSubString = s.substring(start,end);
                }
                char removedChar = s.charAt(start);
                if (tMap.containsKey(removedChar)) {
                    subStrMap.put(removedChar,subStrMap.get(removedChar) - 1);
                }
                start++;
            } else {
                if(end < s.length()) {
                    char newChar = s.charAt(end);
                    if (tMap.containsKey(newChar)) subStrMap.put(newChar,subStrMap.getOrDefault(newChar,0)+1);
                }
                end++;
            }

        }
        // 这个错在哪？  看的懂 while的解法，但是在网课老师优化之前 用 if也能做，逻辑上怎么改？
//        String minSubString = "";
//        HashMap<Character,Integer> tMap = new HashMap<>();
//        for (char c : t.toCharArray()){
//            tMap.put(c,tMap.getOrDefault(c,0)+1);
//        }
//        int start = 0, end = 1;
//        while( end <= s.length()) {
////================================================
////            char newChar = s.charAt(end-1); // 这会导致 在满足条件时 一直往 subStrMap里添加 已经添加过的 end (因为满足覆盖条件时 end不动)
////            if (tMap.containsKey(newChar)) subStrMap.put(newChar,subStrMap.getOrDefault(newChar,0)+1);
////=================================================
//            if (check(tMap,subStrMap)) {
//                if (end-start<minSubString.length() || minSubString.equals("")){
//                    minSubString = s.substring(start,end);
//                }
//                char removedChar = s.charAt(start);
//                if (tMap.containsKey(removedChar)) subStrMap.put(removedChar,subStrMap.get(removedChar)-1);
//                start++;
//            } else {
//                char newChar = s.charAt(end-1);
//                if (tMap.containsKey(newChar)) subStrMap.put(newChar,subStrMap.getOrDefault(newChar,0)+1);
//                end++;
//            }
//        }
        return minSubString;
    }
    public static String temp2(String s, String t) { // 这个错在哪？ 为什么 end指针 到 index = 6(C) 时候就不动了?  【已解决,看注释部分】
        String minSubString = "";
        HashMap<Character,Integer> tMap = new HashMap<>();
        for (char c : t.toCharArray()){
            tMap.put(c,tMap.getOrDefault(c,0)+1);
        }
        int start = 0, end = 1;
        int charCount = 0;
        HashMap<Character,Integer> subStrMap = new HashMap<>();
        while(end <= s.length()) {
            char newChar = s.charAt(end-1);
            if (tMap.containsKey(newChar)){
                subStrMap.put(newChar,subStrMap.getOrDefault(newChar,0)+1);
                if (subStrMap.get(newChar) <= tMap.get(newChar)) charCount++;
            }
            while (charCount==t.length() && start < end) {
                if (end-start<minSubString.length() || minSubString.equals("")){
                    minSubString = s.substring(start,end);
//                    System.out.println(minSubString); // 调试方法 + debug
                }
                char removedChar = s.charAt(start);
                if (tMap.containsKey(removedChar)) {
                    subStrMap.put(removedChar,subStrMap.get(removedChar)-1);
//                    if (subStrMap.get(newChar) < tMap.get(newChar)) charCount--;  // 之前犯的错误
                    if (subStrMap.get(removedChar) < tMap.get(removedChar)) charCount--;
                }
                start++;
            }
            end++;
        }
        return minSubString;
    }
    // 老师给的 if 逻辑解决方案:
    public static String temp3(String s, String t) {
        String minSubString = "";
        HashMap<Character, Integer> tMap = new HashMap<>();
        for (char c : t.toCharArray()) {
            tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        }
        int start = 0, end = 0; // 关键修复1：end初始值改为0
        HashMap<Character, Integer> subStrMap = new HashMap<>();

        while (end <= s.length()) {
            if (check(tMap, subStrMap)) { // 当满足条件时持续收缩
                // 更新最小窗口
                if (minSubString.isEmpty() || end - start < minSubString.length()) {
                    minSubString = s.substring(start, end);
                }
                // 收缩左边界
                char leftChar = s.charAt(start);
                if (tMap.containsKey(leftChar)) {
                    subStrMap.put(leftChar, subStrMap.get(leftChar) - 1);
                    if (subStrMap.get(leftChar) == 0) {
                        subStrMap.remove(leftChar);
                    }
                }
                start++;
            } else {
                // 扩展右边界（先检查end是否越界）
                if (end < s.length()) { // 关键修复2：确保end在有效范围内
                    char newChar = s.charAt(end);
                    if (tMap.containsKey(newChar)) {
                        subStrMap.put(newChar, subStrMap.getOrDefault(newChar, 0) + 1);
                    }
                }
                end++;
            }
        }
        return minSubString;
    }

    // 考虑到 t的字符串大小也可能比较大，遍历总归也会耗时，使用 "贡献值"来优化这一部分。
    public static boolean check(HashMap<Character,Integer> t,HashMap<Character,Integer> subStr) {
        // 遍历 t中每个字符的频次，与 subStr进行比较
        for (char c : t.keySet()) {
            if (subStr.getOrDefault(c,0) < t.get(c)) return false;
        }
        return true;
    }
}
